package com.imooc.distributedemo.leetcode;

/**
 * 找出环形链表开始出现环的位置(下标)--快慢指针
 */
public class FindCircleNode {

    private static ListNode init(){
        ListNode headNode = new ListNode();
        ListNode node = new ListNode(3);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(0);
        ListNode node3 = new ListNode(-4);
        ListNode node4 = new ListNode(8);

        //创建一个链表
        headNode = node;
        node.next = node1;
        node1.next  = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;

        // 3->2->0->-4->8->0  出现环是0->-4->8->0   下标位置为2
        return headNode;
    }

    public static void main(String[] args) {
        ListNode node = init();
        ListNode circleNode = findCircleNode(node);
        System.out.println(circleNode);
    }

    private static ListNode findCircleNode(ListNode head) {
        ListNode fast = head,slow=head;
        while (true) {
            if (fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;
        }
        fast = head;
        //  此时的fast=3->2->0->-4->8->0->-4->8
        // 此时的slow=-4->8->0->-4
        int step = 0;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
            step++;
        }
        return fast;
    }
}
